package cn.njupt.countSort;

import cn.njupt.cmpSort.Sort;

//基数排序的另一种思想
public class RadixSort2 extends Sort<Integer> {
    int[][] arr=null;
    int[] counts=null;
    @Override
    public void sort() {
        arr=new int[array.length][10];
        counts=new int[10];
        int max=array[0];
        for (int i = 1; i < array.length; i++) {
            max=Math.max(max,array[i]);
        }
        for (int i = 1; i <= max; i=i*10) {
            countSort(i);
        }

    }

    public void countSort(int num){
        //最大值为9，最小值为0

        for (int i = 0; i < array.length; i++) {
            arr[counts[array[i]/num%10]++][array[i]/num%10]=array[i];
        }
        //System.out.println(Arrays.toString(counts));
        int index=0;
        for (int i = 0; i < arr[0].length; i++) {
            for(int j=0;j<counts[i];j++){
                array[index++]=arr[j][i];
            }
            counts[i]=0;
        }

    }
}
